Phương pháp đơn giản nhất để kiểm tra một số n {\displaystyle n} có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số m {\displaystyle m} nằm trong khoảng 2 đến n − 1 {\displaystyle n-1} hay không. Nếu n {\displaystyle n} chia hết cho một số m {\displaystyle m} nào đó thì n {\displaystyle n} là hợp số (composite), ngược lại n {\displaystyle n} là số nguyên tố.

Thực ra việc kiểm tra với m {\displaystyle m} từ 2 đến n − 1 {\displaystyle n-1} là không cần thiết, mà chỉ cần kiểm tra đến n {\displaystyle {\sqrt {n}}} . Đó là vì nếu n {\displaystyle n} là hợp số thì nó chắc chắn có ước số không vượt quá n {\displaystyle {\sqrt {n}}} .

Chúng ta cũng có thể bỏ qua việc kiểm tra trường hợp m = 2 {\displaystyle m=2} bằng cách chỉ xét các số lẻ. Đi xa hơn một chút, ta chỉ cần xét các số dạng 6 k ± 1 {\displaystyle 6k\pm 1} và bỏ qua việc kiểm tra 2 trường hợp m = 2 {\displaystyle m=2} và m = 3 {\displaystyle m=3} . Đó là vì tất cả các số nguyên tố đều có dạng 6 k + i {\displaystyle 6k+i} với k {\displaystyle k} nào đó và i = 0 , ± 1 , ± 2 {\displaystyle i=0,\pm 1,\pm 2} ; mà trong đó 6 k + 0 {\displaystyle 6k+0} , 6 k + 2 {\displaystyle 6k+2} , 6 k + 4 {\displaystyle 6k+4} chia hết cho 2, còn 6 k + 3 {\displaystyle 6k+3} thì chia hết cho 3. Tiếp tục với các nhận xét đó, ta có thể tổng quát hóa thành thuật toán sàng Eratosthenes.